package com.dyz.leetcode._11_comprehensiveApplication;

public class _167_twoSum {
    //二分查找
    public int[] twoSum(int[] numbers, int target) {
        if(numbers==null || numbers.length<=1){return new int[2];}

        for (int i=0; i<numbers.length; i++){
            int x = numbers[i];
            //线性查找-0(n)
            //1. 二分查找-o(logn)
            //[i+1, nums.length-1] 区间二分查找 target-1
            int index = binarySrarch(numbers, i+1, numbers.length-1, target-x);
            if(index!=-1){
                return new int[]{i+1, index+1};
            }
        }

        return new int[0];

    }

    private int binarySrarch(int[] numbers, int left, int right, int target) {
        while (left<=right){
            int mid = left+(right-left)/2;
            if(numbers[mid]==target){
                return mid;
            }else if(numbers[mid]>target){
                right = mid -1;
            }else {
                left = left+1;
            }
        }
        return -1;
    }
    //双指针
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    public int[] twoSum1(int[] nums, int target) {
        if (nums == null || nums.length == 0) {return new int[0];}

        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[0];
    }
}
